/**
 * @author João Luís Palma Cardeira - hippie.stereo@gmail.com
 * @version 1.0
 * @date 06/06/2013
 * @copyright (C) :-)
 * @note Applicação para o trabalho de EDA 2012/2013
 * @see main : RunApp
 */
import java.util.Random;

class QuickSortCLS
{

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	protected void QuickSort(double[] listaIn, int posBegin, int posEnd)
	{
		if(posBegin < posEnd)
		{
			int intTemp = Partition(listaIn, posBegin, posEnd);
			QuickSort(listaIn, posBegin, intTemp - 1);
			QuickSort(listaIn, intTemp + 1, posEnd);
		}	
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int Partition(double[] listaIn, int posBegin, int posEnd)
	{
		double x = listaIn[posEnd];
		int indice = posBegin - 1;
		double tempA = 0;
		double tempB = 0;

		for (int j = posBegin; j < posEnd ; j++)
		{
			if (listaIn[j] <= x)
			{
				indice = indice + 1;
				tempA = listaIn[indice];
				listaIn[indice] = listaIn[j];
				listaIn[j] = tempA;	
			}
		}

		tempB = listaIn[indice + 1];
		listaIn[indice + 1] = listaIn[posEnd];
		listaIn[posEnd] = tempB;

		return indice + 1;
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	private int RandomizedPartition(double[] listaIn, int posBegin, int posEnd)
	{
		Random ranCls = new Random();
		int ranIndice = ranCls.nextInt((posEnd - posBegin) + 1) + posBegin;
		// SWAP
		double temp = listaIn[posEnd];
		listaIn[posEnd] = listaIn[ranIndice];
		listaIn[ranIndice] = temp;

		return Partition(listaIn, posBegin, posEnd);
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	protected void RandomizedQuicksort(double[] listaIn, int posBegin, int posEnd)
	{
		if(posBegin < posEnd)
		{
			int posMid = RandomizedPartition(listaIn, posBegin, posEnd);
			RandomizedQuicksort(listaIn, posBegin, posMid - 1);
			RandomizedQuicksort(listaIn, posMid + 1, posEnd);		
		}
	}

	/** 
	 * nomMethode - XXX
	 * @return [description]
	 * @param [parameter-name] [description]
	 * @param [parameter-name] [description]
	 * @exception   Exception1  description de la première exception 
	 * @see UneAutreClasse#UneAutreMethode 
	 */
	
	protected void TailRecursiveQuicksort(double[] listaIn, int posBegin, int posEnd)
	{
		while(posBegin < posEnd)
		{
			int posMid = Partition(listaIn, posBegin, posEnd);
			TailRecursiveQuicksort(listaIn, posBegin, posMid - 1);
			posBegin = posMid + 1;
		}
	}
}